/*
*	队列与宽搜
*/



//N叉树的层序遍历
//https://leetcode.cn/problems/n-ary-tree-level-order-traversal/submissions/
class Solution {
    vector<vector<int>> ret;
    int pos = 0;
public:
    vector<vector<int>> levelOrder(Node* root) {
        if(!root) return {};
        queue<Node*> pq;
        pq.push(root);
        ret.push_back(vector<int>());
        while(!pq.empty())
        {
            int n = pq.size();
            while(n--)
            {
                Node* tmp = pq.front();
                pq.pop();
                ret[pos].push_back(tmp->val);
                int sz = tmp->children.size();
                for(int i = 0;i<sz&&tmp->children[i];++i) pq.push(tmp->children[i]);
            }
            ret.push_back(vector<int>());
            ++pos;
        }

        while(ret.back().size() == 0) ret.pop_back();
        return ret;
    }
};



//二叉树的锯齿形层序遍历
 //https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/submissions/
class Solution {
    vector<vector<int>> ret;
    int pos = 0;
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(!root) return {};
        queue<TreeNode*> pq;
        pq.push(root);
        int layer = 1; //层数从1开始
        while(!pq.empty())
        {
            vector<int> tmp;
            int n = pq.size();
            tmp.reserve(n*(1.5));
            while(n--) //采用堆思想 记录下标计算
            {
                TreeNode* n = pq.front();
                pq.pop();
                tmp.push_back(n->val);
                if(n->left) pq.push(n->left);
                if(n->right) pq.push(n->right);
            }
            if(tmp.empty()) break;
            if((layer++)%2==0) reverse(tmp.begin(),tmp.end()); //判断每一层结果是否需要翻转
            ret.push_back(tmp);
        }
        return ret;
    }
};



 //二叉树最大宽度
 //https://leetcode.cn/problems/maximum-width-of-binary-tree/submissions/
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        unsigned int ret = 1;
        vector<pair<TreeNode*,unsigned int>> grid;
        grid.push_back(make_pair(root,1));

        while(!grid.empty())
        {
            vector<pair<TreeNode*,unsigned int>> tmp;
            tmp.reserve(grid.size()*(1.5));
            for(const pair<TreeNode*,unsigned int>& n:grid)
            {
                if((n.first)->left) tmp.push_back(make_pair((n.first)->left,2*(n.second)));
                if((n.first)->right) tmp.push_back(make_pair((n.first)->right,2*(n.second)+1));
            }
            if(tmp.empty()) break;
            ret = max(ret,(tmp.back().second)-(tmp.front().second)+1);
            tmp.swap(grid);
        }
        return ret;
    }
};


 //在每个树行中找最大值
 //https://leetcode.cn/problems/find-largest-value-in-each-tree-row/submissions/
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(!root) return {};
        list<TreeNode*> pq;
        pq.push_back(root);
        vector<int> ret;
        ret.reserve(1e3);
        while(!pq.empty())
        {
            int maxn = INT_MIN;
            int n = pq.size();
            while(n--)
            {
                TreeNode* node = pq.front();
                maxn=(node->val)>maxn?node->val:maxn;
                pq.pop_front();
                if(node->left) pq.push_back(node->left);
                if(node->right) pq.push_back(node->right);
            }
            ret.push_back(maxn);
        }
        return ret;
    }
};


